/*
 * @lc app=leetcode id=140 lang=cpp
 *
 * [140] Word Break II
 */
class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {

        int len = s.size();
        vector<bool> isBreakable(len+1, false);
        isBreakable[len] = true;

        int minWLen=0, maxWLen=0;
        for (auto& w : wordDict) {
            int wlen = w.size();
            minWLen = std::min(minWLen, wlen);
            maxWLen = std::max(maxWLen, wlen);
        }

        for (int i=len-minWLen; i>=0; i--) {

            int maxGap = std::min(maxWLen, len-i);
            for (int gap=minWLen; gap<=maxGap; gap++) {
                if (isBreakable[i+gap] && std::count(wordDict.begin(), wordDict.end(), s.substr(i, gap))) {
                    isBreakable[i] = true;
                    break;
                }
            }
        }

        vector<string> ret;
        if (isBreakable[0]) {
            vector<string> rec;
            buildWord(s, 0, wordDict, isBreakable, ret, rec, minWLen, maxWLen);
        }
        return ret;
    }

    void buildWord(const string& s, int idx, vector<string>& wordDict, 
            vector<bool>& isBreakable, vector<string>& ret, 
            vector<string>& rec, int minWLen, int maxWLen) {
        int remain = s.size() - idx;
        int maxGap = std::min(maxWLen, remain);
        for (int gap=minWLen; gap<=maxGap; gap++) {
            if (isBreakable[idx+gap] && std::count(wordDict.begin(), wordDict.end(), s.substr(idx, gap))) {
                rec.push_back(s.substr(idx, gap));
                if (idx + gap == s.size()) {
                    pushRet(rec, ret);
                } else {
                    buildWord(s, idx+gap, wordDict, isBreakable, ret, rec, minWLen, maxWLen);
                }
                rec.pop_back();
            }
        }
    }

    void pushRet(vector<string>& slice, vector<string>& ret) {
        int num = slice.size();
        if (num < 1) {
            return ;
        }
        string s = slice[0];
        for (int i=1; i<num; i++) {
            s += " " + slice[i];
        }
        ret.push_back(s);
    }
};

